package me.sealer.algorithm.utils.string;

/**
 * Created by sealer on 17/03/06.
 */
public class StringUtil {

    /**
     * 获取模式串的next数组
     *
     * @param pattern
     * @return
     */
    private int[] getNext(String pattern) {
        int len = pattern.length();
        int j = 0;

        int next[] = new int[len + 1];//next表示长度为i的字符串前缀和后缀的最长公共部分，从1开始
        next[0] = next[1] = 0;

        for (int i = 1; i < len; i++)//i表示字符串的下标，从0开始
        {//j在每次循环开始都表示next[i]的值，同时也表示需要比较的下一个位置
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            next[i + 1] = j;
        }

        return next;
    }
}
